`
https://leetcode.cn/problems/valid-arrangement-of-pairs/
`

/**
 * @param {number[][]} pairs
 * @return {number[][]}
 */
var validArrangement = function (pairs) {
  // 标准欧拉路径模板
  // 构建邻接表，出度入度
  const graph = new Map()
  const inDegree = new Map()
  const outDegree = new Map()
  for (const [from, to] of pairs) {
    if (!graph.has(from)) graph.set(from, [])
    graph.get(from).push(to)
    inDegree.set(to, (inDegree.get(to) || 0) + 1)
    outDegree.set(from, (outDegree.get(from) || 0) + 1)
  }

  // 寻找起点：出度比入度大1or任选
  let start = pairs[0][0]
  for (const node of graph.keys()) {
    if ((outDegree.get(node) || 0) - (inDegree.get(node) || 0) === 1) {
      start = node
      break
    }
  }

  // 获取后序遍历
  const postOrder = []
  function dfs(node) {
    while (graph.get(node) && graph.get(node).length) {
      // 走完删边来避免重复走
      const to = graph.get(node).pop()
      dfs(to)
    }
    postOrder.push(node)
  }
  dfs(start)
  // 翻转后序获得欧拉路径
  postOrder.reverse()

  // 构建为题目需要的结果
  const result = []
  for (let i = 0; i < pairs.length; i++) {
    result.push([postOrder[i], postOrder[i + 1]])
  }
  return result
};